import java.util.ArrayList;

public class Percolation {
  private boolean[][] grid;
  private WeightedQuickUnionUF parents;
  private ArrayList<Integer> blocked_sites;
  private int edge_size;

  /** create N-by-N grid, with all sites blocked */
  public Percolation(int N) {
    grid = new boolean[N][N];
    edge_size = N;
    int i = 0;

    parents = new WeightedQuickUnionUF(N*N);
    blocked_sites = new ArrayList<Integer>(N*N);

    for (int m = 0; m < N; m++)
      for(int n = 0; n < N; n++) {
        grid[m][n] = false;
        blocked_sites.add(i);
        i++;
      }
  }      

  /** open site (row i, column j) if it is not already */
  public void open(int i, int j) {
    //StdOut.printf("x\t= %d, y\t= %d\n", i, j);
    int n_index;
    int index = matrix_to_raw(i, j);
    if(isOpen(i, j))
      return;
    ArrayList<Integer[]> neighbours = get_neighbours(i, j);
    for(int k = 0; k < neighbours.size(); k++)
    {
      n_index = matrix_to_raw(neighbours.get(k)[0], neighbours.get(k)[1]);
      parents.union(index, n_index);
    }
    grid[i][j] = true;
	//StdOut.printf("Removed\t= %d\n", index);    
    blocked_sites.remove(blocked_sites.indexOf(index));
    blocked_sites.trimToSize();
    //StdOut.printf("blocked_sites: \t= %d\n", blocked_sites.size());
  } 

  /** is site (row i, column j) open? */   
  public boolean isOpen(int i, int j) {
    return grid[i][j];
  } 

  /** is site (row i, column j) full? */
  public boolean isFull(int i, int j) {
    int actual_site = matrix_to_raw(i, j);
    int site;

    ArrayList<Integer> top_line = get_top_line();
    for(int k = 0; k < top_line.size(); k++) {
      site = matrix_to_raw(k, 0);

      if(parents.connected(actual_site, site))
        return true;
    }
    return false;
  } 

  /** does the system percolate? */
  public boolean percolates() {
    ArrayList<Integer> bottom_line = get_bottom_line();
    for(int i = 0; i < bottom_line.size(); i++) {
      if(isFull(bottom_line.get(i), edge_size-1))
        return true;
    }
    return false;
  } 

  public double experiment() {
    int raw_index;
    int[] site;
    while(!percolates()) {
      raw_index = get_random_site();
      site = raw_to_matrix(raw_index);

      open(site[0], site[1]);
    }
    return (double)(Math.pow(edge_size, 2) - blocked_sites.size()) / Math.pow(edge_size, 2);
  }
           
  private

  int get_random_site() {
    int r_index = StdRandom.uniform(0, blocked_sites.size());
    return blocked_sites.get(r_index);
  }

  int[] raw_to_matrix(int index) {
    int[] result = new int[2];
    result[0] = index % edge_size;
    result[1] = index / edge_size;
    return result;
  }

  int matrix_to_raw(int i, int j) {
    return j * edge_size + i;
  }

  ArrayList<Integer[]> get_neighbours(int i, int j) {
    ArrayList<Integer[]> neighbours = new ArrayList<Integer[]>(4);
    
    if(i > 0 && grid[i-1][j])
      neighbours.add(new Integer[]{ i-1, j });
    if(i < edge_size-1 && grid[i+1][j])
      neighbours.add(new Integer[]{ i+1, j });
    if(j > 0 && grid[i][j-1])
      neighbours.add(new Integer[]{ i, j-1 });
    if(j < edge_size-1 && grid[i][j+1])
      neighbours.add(new Integer[]{ i, j+1 });

    neighbours.trimToSize();

    return neighbours;
  }

  ArrayList<Integer> get_bottom_line() {
    ArrayList<Integer> line = new ArrayList<Integer>(edge_size);

    for(int i = 0; i < edge_size; i++)
      if(grid[i][edge_size-1])
        line.add(i);
    line.trimToSize();
    return line;
  }

  ArrayList<Integer> get_top_line() {
    ArrayList<Integer> line = new ArrayList<Integer>(edge_size);

    for(int i = 0; i < edge_size; i++)
      if(grid[i][0])
        line.add(i);
    line.trimToSize();
    return line;
  }
}
